package com.zry.demo;

import java.util.Arrays;

/**
 * 实现思路 数组 + 递归思路
 */
public class YueSeFu {
    /**
     * 数组实现约瑟夫杀人问题
     * @param arr 数组的总个数代表总人数，数组中每一个都是1，代表或者， 0代表死亡
     * @param lastKillIndex 上一次的杀的人的下标
     * @param killNum 每隔几个杀人
     * @return 只留了一个活人的数组
     */
    private int[] kill(int[] arr, int lastKillIndex, int killNum) {
        if (arr == null) {
            return null;
        }

        if (allLiveCount(arr) == 1) {
            return arr;
        } else {
            //定于将要杀得人的索引，从上一个被杀的人下面一个人开始
            int killIndex = lastKillIndex + 1;

            //边界处理 如果已经到达末尾，就切换到开头，如此循环
            if (killIndex >= arr.length) {
                killIndex = 0;
            }

            //碰到的第几个活人，可能是已经循环多轮的情况，下一个索引碰到可能是已经被杀死的人
            int meetLive = 0;
            while (meetLive < killNum) {
                //如果碰到活人，就+1， 如果碰到第killNum个活人就停止，这个位置就是要杀的位置
                if(arr[killIndex] == 1){
                    meetLive++;
                }
                //最后一个活人的索引就是要被杀的位置，不需再增加
                if (meetLive != killNum) {
                     killIndex++;
                    if (killIndex >= arr.length) {
                        killIndex = 0;
                    }
                }
            }

            System.out.println("killIndex=" + killIndex);
            //将该位置的人杀死
            arr[killIndex] = 0;
            //更新最近的一个被杀死的人位置
            lastKillIndex = killIndex;
            return kill(arr, lastKillIndex, killNum);
        }
    }

    /**
     * 计算目前活着的人的数量，也可以定义一个全部变量，每杀死一个人递减
     * @param arr
     * @return
     */
    private int allLiveCount(int[] arr) {
        int live = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                live++;
            }
        }
        return live;
    }

    /**
     * 查找唯一活着的人索引
     * @param arr
     * @return
     */
    private int findLastLiveIndex(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 生成指定数量活人的数组
     * @param allPeopleNum
     * @return
     */
    private int[] generateArr(int allPeopleNum) {
        int[] arr = new int[allPeopleNum];
        Arrays.fill(arr, 1);
        return arr;
    }

    public static void main(String[] args) {
        YueSeFu yueSeFu = new YueSeFu();
        int[] arr = yueSeFu.generateArr(24);
        //一开始未杀人，所以传入-1作为初始被杀人的下标
        arr = yueSeFu.kill(arr, -1, 3);
        if (arr == null) {
            System.out.println("入参错误");
            return;
        }
        int liveIndex = yueSeFu.findLastLiveIndex(arr);
        System.out.println("liveIndex=" + liveIndex);
        System.out.println("people num=" + (liveIndex + 1));
    }
}